package exercises.leetcode;

/**
 * <a href="https://leetcode-cn.com/problems/maximum-sum-circular-subarray/">
 * 918. 环形子数组的最大和</a>
 *
 * <p><span color="#87CEEB">描述:</span>
 * 给定一个由整数数组 A 表示的环形数组 C，求 C 的非空子数组的最大可能和。
 * <p>
 * 在此处，环形数组意味着数组的末端将会与开头相连呈环状。（形式上，当0 <= i < A.length 时 C[i] = A[i]，且当 i >= 0 时 C[i+A.length] = C[i]）
 * <p>
 * 此外，子数组最多只能包含固定缓冲区 A 中的每个元素一次。（形式上，对于子数组 C[i], C[i+1], ..., C[j]，不存在 i <= k1, k2 <= j 其中 k1 % A.length = k2 % A.length）
 *
 * @author or2
 * @date 2021年10月09日 时间: 23:18
 */
public class No918 {
    public int maxSubarraySumCircular(int[] nums) {
        int length = nums.length;
        int[] mins = new int[length];
        System.arraycopy(nums, 0, mins, 0, length);

        int sum = nums[0], max = nums[0], min = nums[0];
        for (int i = 1; i < length; i++) {
            sum += nums[i];
            nums[i] = Math.max(nums[i - 1] + nums[i], nums[i]);
            if (nums[i] > max)
                max = nums[i];
            mins[i] = Math.min(mins[i - 1] + mins[i], mins[i]);
            if (mins[i] < min)
                min = mins[i];
        }

        if (sum == min)
            return max;
        return Math.max(max, sum - min);
    }
}
